It is instrumental for many applications to have a block that adds n inputs of the same binary weight together. An output of this block is a binary representation of the number of high inputs. Such blocks, called parallel counters (L. Dadda, Some Schemes for Parallel Multipliers, Alta Freq 34: 349-356 (1965); E. E. Swartzlander Jr., Parallel Counters, IEEE Trans. Comput. C-22: 1021-1024 (1973)) (the content of which is hereby incorporated by reference), are used in circuits performing binary multiplication. There are other applications of a parallel counter, for instance, majority-voting decoders or RSA encoders and decoders. It is important to have an implementation of a parallel counter that achieves a maximal speed. It is known to use parallel counters in multiplication (L. Dadda, On Parallel Digital Multipliers, Alta Freq 45: 574-580 (1976)) (the content of which is hereby incorporated by reference).
A full adder is a special parallel counter with a three-bit input and a two-bit output. A current implementation of higher parallel counters i.e. with a bigger number of inputs is based on using full adders (C. C. Foster and F. D. Stockton, Counting Responders in an Associative Memory, IEEE Trans. Comput. C-20: 1580-1583 (1971)) (the content of which is hereby incorporated by reference). In general, the least significant bit of an output is the fastest bit to produce in such implementation while other bits are usually slower.
The following notation is used for logical operations:                ⊕—Exclusive OR;        —OR;        —AND;        —NOT.        
An efficient prior art design (Foster and Stockton) of a parallel counter uses full adders. A full adder, denoted FA, is a three-bit input parallel counter shown in FIG. 1. It has three inputs X1, X2, X3, and two outputs S and C. Logical expressions for outputs areS=X1⊕X2⊕X3,C=(X1X2)(X1X3)(X2X3).
A half adder, denoted HA, is a two bit input parallel counter shown in FIG. 1. It has two inputs X1, X2 and two outputs S and C. Logical expressions for outputs areS=X1⊕X2,C=X1AX2.
A prior art implementation of a seven-bit input parallel counter illustrated in FIG. 2.
A paper by Irving T. To and Tien Chi Chen entitled “Multiple Addition by Residue Threshold Functions and Their Representation by Array Logic” (IEEE Trans. Comput. C-22:762-767 (1973)) (the content of which is hereby incorporated by reference) discloses a method of adding together a collection of numbers using exact symmetric functions to implement residue threshold functions. This arrangement provides some improvement in speed over conventional full adders but requires a large increase in area due to the need to compute exactly.
Multiplication is a fundamental operation. Given two n-digit binary numbersAn−12n−1+An−22n−2+ . . . +A12+A0 and Bn−12n−1+Bn−22n−2+ . . . +B12+B0,their productP2n−122n−1+P2n−222n−2+ . . . +P12+P0may have up to 2n digits. Logical circuits generating all Pi as outputs generally follow the scheme in FIG. 14. Wallace has invented the first fast architecture for a multiplier, now called the Wallace-tree multiplier (Wallace, C. S., A Suggestion for a Fast Multiplier, IEEE Trans. Electron. Comput. EC-13: 14-17 (1964)) (the content of which is hereby incorporated by reference). Dadda has investigated bit behaviour in a multiplier (L. Dadda, Some Schemes for Parallel Multipliers, Alta Freq 34: 349-356 (1965)) (the content of which is hereby incorporated by reference). He has constructed a variety of multipliers and most parallel multipliers follow Dadda's or Wallace's scheme.
Dadda's multiplier uses the scheme in on FIG. 22. If inputs have 8 bits then 64 parallel AND gates generate an array shown in FIG. 23. The AND gate Sign  is omitted for clarity so that AiBj becomes AiBj. The rest of FIG. 23 illustrates array reduction that involves full adders (FA) and half adders (HA). Bits from the same column are added by half adders or full adders. Some groups of bits fed into a full adder are in rectangles. Some groups of bits fed into a half adder are in ovals. The result of array reduction is just two binary numbers to be added at the last step. One adds these two numbers by one of the fast addition schemes, for instance, conditional adder or carry-look-ahead adder.